package com.shuang.backtracking7;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses {

    //全局变量存放结果
    List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {

        //总长度大于12一定不符合ip规定直接返回
        if (s.length() > 12) {
            return res;
        }

        //将字符串 s 转为 sb 操作字符串方便 快速
        StringBuilder sb = new StringBuilder(s);

        //处理
        backTracking(sb, 0, 0);

        return res;
    }

    //dotNum 代表用于分割ip数字的 逗点数量
    private void backTracking(StringBuilder sb, int startIndex, int dotNum) {

        //终止条件
        if (dotNum == 3) {
            //三个逗点证明被分成了四段
            //判断第四段数字是否符合规定
            //符合规定将此正确ip加入结果中保存
            if (isValid(sb, startIndex, sb.length() - 1)) {
                res.add(sb.toString());
            }
            return;
        }

        //for
        for (int i = startIndex; i < sb.length(); i++) {
            //判断分隔的子区间[start, i]的数字是否符合规定
            if (isValid(sb, startIndex, i)) {
                //符合规定进行处理
                //字符串i的位置后面加上逗点
                sb.insert(i + 1, ".");

                //逗点数量加一
                dotNum++;

                //递归 开始索引从i+2的位置开始（字符串多了一个 . ）
                backTracking(sb, i + 2, dotNum);

                //回溯
                sb.deleteCharAt(i + 1);//删除逗点
                dotNum--;
            }
        }
    }

    //判断数字字符串是否符合ip规定 区间[start, end]
    //段位以0为开头的数字不合法
    // 段位里有非正整数字符不合法
    // 段位如果大于255了不合法
    private boolean isValid(StringBuilder s, int start, int end) {
        if (start > end)
            return false;
        if (s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for (int i = start; i <= end; i++) {

            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到非数字字符不合法
                return false;
            }

            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if (num > 255)
                return false;
        }
        return true;
    }
}
